package algorithm.tree;


import algorithm.Node;
import org.springframework.context.annotation.Bean;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 判断一棵树是否搜索二叉树
 *
 * @author csp 2021-12-12
 */
public class Code02_CheckSearchTree {

    /*
        左树节点小
        右树节点大
        每一颗子树都满足
     */


    private static int preValue = Integer.MIN_VALUE;

    /**
     * 中序遍历
     * 递归方式
     *
     * @return
     */
    public boolean checkBST(Node head) {
        if (head == null) {
            return true;
        }
        boolean isLeftBst = checkBST(head.left);

        if (head.val <= preValue) {
            return false;
        } else {
            preValue = head.val;
        }

        return checkBST(head.right);


    }


    /**
     * 中序遍历
     *
     */
    static List<Integer> list = new ArrayList<>();
    public static void checkBST2(Node head) {
        if (head == null) {
            return;
        }
        checkBST2(head.left);
        list.add(head.val);
        checkBST2(head.right);
    }

    /**
     * 非递归方式
     *
     *
     * @param head
     */
    @Bean(initMethod = "")
    public static boolean checkBST3(Node head) {
        if (head == null) {
            return true;
        }
        Stack<Node> stack = new Stack<>();

        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (head.val <= preValue) {
                    return false;
                } else {
                    preValue = head.val;
                }
            }

        }
        return true;

    }

    // 完全


}
